When digital messages are transmitted over telecommunication networks some errors can be expected and to insure data integrity, the serialized data is protected with Error Detection Codes. In modern high speed networks the lines have a low error rate and the security of data only requires a end to end process. The data integrity process is carried out at both the sending and the receiving station; the sending station calculates a code corresponding to the data and the transmitting station checks the integrity of the data and code. ATM uses Frame Check Sequence (FCS) field derived from Cyclic Redundancy Check (CRC) Error Detection codes for error checking. The CRC codes are often used for checking integrity of data because they are easy to implement and they detect a wide range of errors. The access nodes of an ATM network having the responsibility of data integrity, the originating node calculates the redundancy bits constituting the Frame Check Sequence, (FCS) which is appended by the originating system to the bit stream to be checked before sending it over the network. At the end node, a new FCS is computed on the bit stream plus its initial FCS. There is no error in transmission if the computed FCS at the end node yields a constant value depending on the type of CRC used.
CRC codes are generated by a generator polynomial characterizing the type of CRC; the CRC code corresponding to the polynomial representation of a bit stream to be encoded is the remainder of the polynomial division of the polynomial representation of the bit stream by the polynomial generator; CRC calculations are described, for instance, in `Teleinformatique I` of Henri Nussbaumer, 1987, Presses informatiques romandes CH-1015 Lausanne. The FCS code has been standardized for data integrity checking as described in the ANSI X3.139-1987 document pages 28 and 29 and in the Appendix B. All the CRC codes constitute a finite mathematical multiplying group. If the polynomial generator is of degree d and if it is irreducible, the finite group constitutes a Galois Field having 2.sup.d -1 elements. The facility of implementing codes based on CRC is due to the simple characteristics of calculations in the finite Galois Fields.
In ATM networks different types of connections between two end points may be established depending on the quality of service required. The ATM Forum organization followed by the ATM network industry and some ATM standards organizations (ITU-T The International Telecommunication Union-Telecommunication and ETSI The European Telecommunication Standardization Institute) have standardized different ATM Adaptation Layers (AALS) to provide generalized interworking across the ATM network. This AAL function is implemented in the ATM end point which connects to the ATM network over the User Network Interface (UNI). As ATM switches usually contain endpoint functions as well as switch functions, AAL function is also implemented in ATM switches. In the case of data, this AAL function takes frames (blocks) of data delivered to the ATM network, breaks them up into cells and adds necessary header information to allow rebuilding of the original block at the receiver. Different AALs correspond to different traffic types. For instance, if AAL1 is used for the service class A, circuit emulation, AAL3/4 provides an end-to-end transport for both connection oriented (class C) and connectionless data (class D).
The ATM cell headers have their own error checking based on FCS calculation. The payload of 384 bits (48 bytes) of some ATM cells uses FCS redundancy bits for error checking; The AAL3/4 cell payload error checking is based on the CRC-10 codes generated by the generator polynomial of degree 10: EQU G(X)=X.sup.10 +X.sup.9 +X.sup.5 +X.sup.4 +X+1
The ATM Operations Administration and Maintenance (OA&M) cell payload also uses FCS redundancy bits for error checking based on CRC-10 codes. The OA&M cells are used for supporting protocols specified as part of the ATM layer designed to dynamically test ATM connections, links, virtual Channels, Virtual Paths and links. These protocols perform the functions of performance monitoring, defect and failure detection, system protection, failure or performance information and fault isolation. These functions must be performed by the management system in an ATM network according to the ATM forum recommendations.
The polynomial representation of a CRC-10 code of a bit stream represented by the polynomial P(X) is the remainder of the polynomial division of P(X) by the generator polynomial G(X) Assuming the CRC-10 code of a data bits stream represented by the polynomial Ps(X) is Rem.sub.G (PA(X) the corresponding FCS code based on CRC-10 is: EQU FCS (P(X))=Rem.sub.G (X.sup.10 P(X)+X.sup.k L(X))
k=degree of p(x) PA1 L (X)=X.sup.10 +X.sup.9 + . . . +X.sup.2 +X+1 PA1 is the sign of the polynomial multiplication in the Galois Field. It is a two step operation comprising a first step to multiply the two polynomials and a second step to take the remainder of the result in the division by G. PA1 .alpha. at is an irreducible polynomial, root of the Galois Field generated by G. PA1 .alpha..sup.8 is the 9th element of the Galois Field (simple element having only one coefficient equal to 1 in its polynomial representation). PA1 calculating (520) CRC code generated by the polynomial generator of degree 9, G9(X)=X.sup.9 +X.sup.4 +1, of the packet payload and storing the resulting 9-bit stream FCS in 9-bit storage means; PA1 calculating (510) the parity of said payload; setting (580) the most significant bot of the 10-bit storage means to zero; PA1 if the payload parity is odd (590), adding (597) the 9-bit stream FCS to a bit stream representation of the generator polynomial of degree 9, G9(X); and PA1 if the payload parity is even, storing (595) the 9-bit stream FCS in the least significant bits of the 10-bit storage means, the 10-bit stream of the 10-bit storage means representing the payload FCS that was to be calculated.
The standard circuitry for computing the FCS of a message is a Linear Feedback Shift Register (LFSR) which carries out a bit by bit multiplication in the Galois Field. Each bit of the message is pushed in the LFSR, Most Significant Bit (MSB) first. The division is performed by the feedbacks. At the end of the process, the FCS (remainder of the division) is within the shift register. This method and type of circuitry is described, for instance in `Error Checking Codes` by Peterson and Weldon, the MIT Press, 2nd edition, 1972. Although simple the method suffers drawbacks since only one bit is processed at each shift as many shifts as the number of bits is the message is needed in the LFSR. As the 10 bits CRC is used, a 10-bit register is needed. Therefore computing the CRC takes as many clock pulses as there are bits in the message.
A faster CRC calculation is provided in the patent application published under the reference EP 0614 294 entitled `Method for generating a frame check sequence` disclosing a one (or more) byte(s) based FCS calculation, this method being more efficient than a bit based FCS calculation as with the LFSRs. This patent application takes advantage of the properties of the operations in the Galois Fields. One property of the Galois Field is to have a root .alpha., an irreducible polynomial element of the Galois Field, characterized in that each element of the Galois Field is represented by .alpha..sup.d, d being one integer greater or equal to zero and smaller than the number of elements of the Galois Field. According to the preferred embodiment of the cited patent application, the calculation of FCS of a byte stream can be performed byte by byte, each new byte read being XORed with the result of the multiplication of the previous FCS value by the .alpha..sup.8 element of the Galois Field. The multiplier is the implementation of the .alpha..sup.8 multiplication in the Galois Field, this means modulo the polynomial generator G(X). The mathematical formula illustrating the method is expressed in the Galois Field as follows: EQU FCS(N+1)=FCS(N).alpha..sup.8 +B(N+1) (expression 1)
Where FCS(N) is the FCS of the message consisting of the N previous bytes, B(N+1) the polynomial representation of the next byte (new byte) of the message.
This per byte calculation of the FCS is implemented using a Multiplier adder implemented in adapter cards of the ATM access nodes. The same method can be used also for this calculation while handling any number of bits at a time consequently improving the processing time. However, with the method of the prior art and the current technologies, it is very difficult to perform the FCS calculations for data integrity checking of cell payload while sustaining media speed particularly over OC3 links (155 Mbps which allows 2.8 .mu.s to process the cell).
It is the object of the invention to simplify and reduce process time of cell payload FCS calculations such as those performed in an ATM access node sending OA&M or AAL3/4 types of cells on the ATM network. The same performance improvement should apply to the process of checking the OA&M or AAL3/4 cell payload FCS in the access node at cell reception.